1. Field of the Invention
This invention relates to systems having shared resources and more particularly to arbitrating multiple requests for multiple resources is such systems.
2. Description of the Related Art
Systems having shared resources are common. In many such systems, arbiters have to schedule usage of the shared resources to prevent conflicts resulting from requests for simultaneous access to the same shared resource. One example of such a system having shared resources susceptible to conflicts is a cross bar switch having multiple input ports and multiple output ports in which input ports make requests for connection to the output ports. Each requester or input port sends a request for an output port or a set of requests for multiple output ports to an arbiter. A particular output port may be requested by multiple input ports at the same time. Assuming an output port can be allocated to only one input port at a time, an arbitration decision is made to award the output port to one of the requesters. The arbiter chooses the requests to be granted such that resources (the output ports) are allocated to requesters in a conflict-free way. Thus, certain requests are serviced by being granted an output port and certain requests may be left unserviced in that they are denied an output port. However, the choice of which requests to grant may lead to under-utilization of the resources since some requests may be denied.
Another example of a system having shared resources is a computer system in which multiple processors are coupled to multiple memories. Assume that each processor has access to all of the memories and each memory can only be accessed by one processor at a time. When multiple processors request access to the same memory at the same time an arbitration decision has to be made as to which processor gets to access the memory in question.
While numerous arbitration schemes have been developed to try and provide fair and efficient allocation of system resources for scheduling problems that involve multiple requesters requesting multiple shared resources such as the crossbar switch or multi-processor system described above, it would be desirable to have an improved arbitration scheme that provides for high aggregate usage of the shared resources while still providing a minimum level of fairness.